The hardness and approximation algorithms for l%2Ddiversity.
The existing solutions to privacy preserving publication can be classified into the theoretical and heuristic categories. The former guarantees provably low information loss, whereas the latter incurs gigantic loss in the worst case, but is shown empirically to perform well on many real inputs. While numerous heuristic algorithms have been developed to satisfy advanced privacy principles such as l-diversity, t-closeness, etc., the theoretical category is currently limited to k-anonymity which is the earliest principle known to have severe vulnerability to privacy attacks. Motivated by this, we present the first theoretical study on l-diversity, a popular principle that is widely adopted in the literature. First, we show that optimal l-diverse generalization is NP-hard even when there are only 3 distinct sensitive values in the microdata. Then, an (l · d)approximation algorithm is developed, where d is the dimensionality of the underlying dataset. This is the first known algorithm with a non-trivial bound on information loss. Extensive experiments with real datasets validate the effectiveness and efficiency of proposed solution. 1.
Correlation hiding by independence masking.


Logging every footstep quantile summaries for the entire history.
Quantiles are a crucial type of order statistics in databases. Extensive research has been focused on maintaining a space-efficient structure for approximate quantile computation as the underlying dataset is updated. The existing solutions, however, are designed to support only the current, most-updated, snapshot of the dataset. Queries on the past versions of the data cannot be answered. This paper studies the problem of historical quantile search. The objective is to enable ɛ-approximate quantile retrieval on any snapshot of the dataset in history. The problem is very important in analyzing the evolution of a distribution, monitoring the quality of services, query optimization in temporal databases, and so on. We present the first formal results in the literature. First, we prove a novel theoretical lower bound on the space cost of supporting ɛ-approximate historical quantile queries. The bound reveals the fundamental difference between answering quantile queries about the past and those about the present time. Second, we propose a structure for finding ɛ-approximate historical quantiles, and show that it consumes more space than the lower bound by only a squarelogarithmic factor. Extensive experiments demonstrate that in practice our technique performs much better than predicted by theory. In particular, the quantiles it returns are remarkably more accurate than the theoretical precision guarantee.

Transparent anonymization Thwarting adversaries who know the algorithm.

Efficient and accurate nearest neighbor and closest pair search in high%2Ddimensional space.

Transparent Anonymization Thwarting Adversaries Who Know the Algorithm


Superseding Nearest Neighbor Search on Uncertain Spatial Databases.
This paper proposes a new problem, called superseding nearest neighbor search, on uncertain spatial databases, where each object is described by a multidimensional probability density function. Given a query point q, an object is a nearest neighbor (NN) candidate if it has a non-zero probability to be the NN of q. Given two NN candidates o1 and o2, o1 supersedes o2 if o1 is more likely to be closer to q. An object is a superseding nearest neighbor (SNN) of q, if it supersedes all the other NN-candidates. Sometimes no object is able to supersede every other NN candidate. In this case, we return the SNNcore — the minimum set of NN-candidates each of which supersedes all the NN-candidates outside the SNN-core. Intuitively, the SNN-core contains the best objects, because any object outside the SNN-core is worse than all the objects in the SNN-core. We show that the SNN-core can be efficiently computed by utilizing a conventional multidimensional index, as confirmed by extensive experiments.



Continuous privacy preserving publishing of data streams.
Recently, privacy preserving data publishing has received a lot of attention in both research and applications. Most of the previous studies, however, focus on static data sets. In this paper, we study an emerging problem of continuous privacy preserving publishing of data streams which cannot be solved by any straightforward extensions of the existing privacy preserving publishing methods on static data. To tackle the problem, we develop a novel approach which considers both the distribution of the data entries to be published and the statistical distribution of the data stream. An extensive performance study using both real data sets and synthetic data sets verifies the effectiveness and the efficiency of our methods. 1.
Finding frequent co%2Doccurring terms in relational keyword search.

Privacy Preserving Publishing on Multiple Quasi%2Didentifiers.

Scalable Keyword Search on Large Data Streams.

Uncertain Location Based Range Aggregates in a Multi%2Ddimensional Space.
Abstract — Uncertain data are inherent in many applications such as environmental surveillance and quantitative economics research. Recently, considerable research efforts have been put into the field of analysing uncertain data. In this paper, we study the problem of processing the uncertain location based range aggregate in a multi-dimensional space. We first formally introduce the problem, then propose a general filtering-and-verification framework to solve the problem. Two filtering techniques, named STF and PCR respectively, are proposed to signficantly reduce the verification cost. I.
Querying Communities in Relational Databases.
Abstract — Keyword search on relational databases provides users with insights that they can not easily observe using the traditional RDBMS techniques. Here, an l-keyword query is specified by a set of l keywords, {k1, k2,  ·  ·  · , kl}. It finds how the tuples that contain the keywords are connected in a relational database via the possible foreign key references. Conceptually, it is to find some structural information in a database graph, where nodes are tuples and edges are foreign key references. The existing work studied how to find connected trees for an l-keyword query. However, a tree may only show partial information about how those tuples that contain the keywords are connected. In this paper, we focus on finding communities for an l-keyword query. A community is an induced subgraph that contains all the l-keywords within a given distance. We propose new efficient algorithms to find all/top-k communities which consume small memory, for an l-keyword query. For topk l-keyword queries, our algorithm allows users to interactively enlarge k at run time. We conducted extensive performance studies using two large real datasets to confirm the efficiency of our algorithms. I.
Distance%2DBased Representative Skyline.
Abstract — Given an integer k, arepresentative skyline contains the k skyline points that best describe the tradeoffs among different dimensions offered by the full skyline. Although this topic has been previously studied, the existing solution may sometimes produce k points that appear in an arbitrarily tiny cluster, and therefore, fail to be representative. Motivated by this, we propose a new definition of representative skyline that minimizes the distance between a non-representative skyline point and its nearest representative. We also study algorithms for computing distance-based representative skylines. In 2D space, there is a dynamic programming algorithm that guarantees the optimal solution. For dimensionality at least 3, we prove that the problem is NP-hard, and give a 2-approximate polynomial time algorithm. Using a multidimensional access method, our algorithm can directly report the representative skyline, without retrieving the full skyline. We show that our representative skyline not only better captures the contour of the entire skyline than the previous method, but also can be computed much faster. I.
Indexing uncertain data.
In this paper, we will examine the problem of distance function computation and indexing uncertain data in high dimensionality for nearest neighbor and range queries. Because of the inherent noise in uncertain data, traditional distance function measures such as the Lqmetric and their probabilistic variants are not qualitatively effective. This problem is further magnified by the sparsity issue in high dimensionality. In this paper, we examine methods of computing distance functions for high dimensional data which are qualitatively effective and friendly to the use of indexes. In this paper, we show how to construct an effective index structure in order to handle uncertain similarity and range queries in high dimensionality. Typical range queries in high dimensional space use only a subset of the ranges in order to resolve the queries. Furthermore, it is often desirable to run similarity queries with only a subset of the large number of dimensions. Such queries are difficult to resolve with traditional index structures which use the entire set of dimensions. We propose query-processing techniques which use effective search methods on the index in order to compute the final results. We discuss the experimental results on a number of real and synthetic data sets in terms of effectiveness and efficiency. We show that the proposed distance measures are not only more effective than traditional Lq-norms, but can also be computed more efficiently over our proposed index structure. 1
Quality and efficiency in high dimensional nearest neighbor search.
Nearest neighbor (NN) search in high dimensional space is an important problem in many applications. Ideally, a practical solution (i) should be implementable in a relational database, and (ii) its query cost should grow sub-linearly with the dataset size, regardless of the data and query distributions. Despite the bulk of NN literature, no solution fulfills both requirements, except locality sensitive hashing (LSH). The existing LSH implementations are either rigorous or adhoc. Rigorous-LSH ensures good quality of query results, but requires expensive space and query cost. Although adhoc-LSH is more efficient, it abandons quality control, i.e., the neighbor it outputs can be arbitrarily bad. As a result, currently no method is able to ensure both quality and efficiency simultaneously in practice. Motivated by this, we propose a new access method called the locality sensitive B-tree (LSB-tree) that enables fast highdimensional NN search with excellent quality. The combination of several LSB-trees leads to a structure called the LSB-forest that ensures the same result quality as rigorous-LSH, but reduces its space and query cost dramatically. The LSB-forest also outperforms adhoc-LSH, even though the latter has no quality guarantee. Besides its appealing theoretical properties, the LSB-tree itself also serves as an effective index that consumes linear space, and supports efficient updates. Our extensive experiments confirm that the LSB-tree is faster than (i) the state of the art of exact NN search by two orders of magnitude, and (ii) the best (linear-space) method of approximate retrieval by an order of magnitude, and at the same time, returns neighbors with much better quality.
Reverse Nearest Neighbor Query.
In this paper, we discuss static and dynamic data structures for answering reverse nearest neighbor queries in two dimensions.
Spatio%2DTemporal Data Warehouses.
Spatio-temporal databases store information about the positions of individual objects over time. In many applications however, such as traffic supervision or mobile communication systems, only summarized data, like the average number of cars in an area for a specific period, or phones serviced by a cell each day, is required. Although this information can be obtained from operational databases, its computation is expensive, rendering online processing inapplicable. A vital solution is the construction of a spatiotemporal data warehouse. In this paper, we describe a framework for supporting OLAP operations over spatiotemporal data. We argue that the spatial and temporal dimensions should be modeled as a combined dimension on the data cube and present data structures, which integrate spatiotemporal indexing with pre-aggregation. While the well-known materialization techniques require a-priori knowledge of the grouping hierarchy, we develop methods that utilize the proposed structures for efficient execution of ad-hoc group-bys. Our techniques can be used for both static and dynamic dimensions.  1. 
The Hardness and Approximation Algorithms for L%2DDiversity
The existing solutions to privacy preserving publication can be classified into the theoretical and heuristic categories. The former guarantees provably low information loss, whereas the latter incurs gigantic loss in the worst case, but is shown empirically to perform well on many real inputs. While numerous heuristic algorithms have been developed to satisfy advanced privacy principles such as l-diversity, t-closeness, etc., the theoretical category is currently limited to k-anonymity which is the earliest principle known to have severe vulnerability to privacy attacks. Motivated by this, we present the first theoretical study on l-diversity, a popular principle that is widely adopted in the literature. First, we show that optimal l-diverse generalization is NP-hard even when there are only 3 distinct sensitive values in the microdata. Then, an (l · d)approximation algorithm is developed, where d is the dimensionality of the underlying dataset. This is the first known algorithm with a non-trivial bound on information loss. Extensive experiments with real datasets validate the effectiveness and efficiency of proposed solution. 1.
Diversity in Skylines.
Given an integer k, a diverse skyline contains the k skyline points that best describe the tradeoffs (among different dimensions) offered by the full skyline. This paper gives an overview of the latest results on this topic. Specifically, we first describe the state-of-the-art formulation of diverse skylines. Then, we explain several algorithms for finding a diverse skyline, where the objective is to save cost by avoiding the computation of the entire skyline. In particular, we will discuss a polynomial-time algorithm in 2D space that returns the exact result, the NP-hardness of the problem in dimensionality at least 3, and an approximate solution with good quality guarantees. 1
Efficient Evaluation of Probabilistic Advanced Spatial Queries on Existentially Uncertain Data.
Abstract—We study the problem of answering spatial queries in databases where objects exist with some uncertainty and they are associated with an existential probability. The goal of a thresholding probabilistic spatial query is to retrieve the objects that qualify the spatial predicates with probability that exceeds a threshold. Accordingly, a ranking probabilistic spatial query selects the objects with the highest probabilities to qualify the spatial predicates. We propose adaptations of spatial access methods and search algorithms for probabilistic versions of range queries, nearest neighbors, spatial skylines, and reverse nearest neighbors and conduct an extensive experimental study, which evaluates the effectiveness of proposed solutions. Index Terms—H.2.4.h Query processing, H.2.4.k Spatial databases 1
Cost%2DBased Predictive Spatiotemporal Join.

Distributed Skyline Retrieval with Low Bandwidth Consumption.
We consider skyline computation when the underlying dataset is horizontally partitioned onto geographically distant servers that are connected to the Internet. The existing solutions are not suitable for our problem, because they have at least one of the following drawbacks: (i) applicable only to distributed systems adopting vertical partitioning or restricted horizontal partitioning, (ii) effective only when each server has limited computing and communication abilities, and (iii) optimized only for skyline search in subspaces but inefficient in the full space. This paper proposes an algorithm, called feedback-based distributed skyline (FDS), to support arbitrary horizontal partitioning. FDS aims at minimizing the network bandwidth, measured in the number of tuples transmitted over the network. The core of FDS is a novel feedback-driven mechanism, where the coordinator iteratively transmits certain feedback to each participant. Participants can leverage such information to prune a large amount of local data, which otherwise would need to be sent to the coordinator. Extensive experimentation confirms that FDS significantly outperforms alternative approaches in both effectiveness and progressiveness.
ANGEL Enhancing the Utility of Generalization for Privacy Preserving Publication.
Generalization is a well-known method for privacy preserving data publication. Despite its vast popularity, it has several drawbacks such as heavy information loss, difficulty of supporting marginal publication, and so on. To overcome these drawbacks, we develop ANGEL 1, a new anonymization technique that is as effective as generalization in privacy protection, but is able to retain significantly more information in the microdata. ANGEL is applicable to any monotonic principles (e.g., l-diversity, t-closeness, etc.), with its superiority (in correlation preservation) especially obvious when tight privacy control must be enforced. We show that ANGEL lends itself elegantly to the hard problem of marginal publication. In particular, unlike generalization that can release only restricted marginals, our technique can be easily used to publish any marginals with strong privacy guarantees.
Optimal Random Perturbation at Multiple Privacy Levels.
Random perturbation is a popular method of computing anonymized data for privacy preserving data mining. It is simple to apply, ensures strong privacy protection, and permits effective mining of a large variety of data patterns. However, all the existing studies with good privacy guarantees focus on perturbation at a single privacy level. Namely, a fixed degree of privacy protection is imposed on all anonymized data released by the data holder. This drawback seriously limits the applicability of random perturbation in scenarios where the holder has numerous recipients to which different privacy levels apply. Motivated by this, we study the problem of multi-level perturbation, whose objective is to release multiple versions of a dataset anonymized at different privacy levels. The challenge is that various recipients may collude by sharing their data to infer privacy beyond their permitted levels. Our solution overcomes this obstacle, and achieves two crucial properties. First, collusion is useless, meaning that the colluding recipients cannot learn anything more than what the most trustable recipient (among the colluding recipients) already knows alone. Second, the data each recipient receives can be regarded (and hence, analyzed in the same way) as the output of conventional uniform perturbation. Besides its solid theoretical foundation, the proposed technique is both space economical and computationally efficient. It requires O(n+m) expected space, and produces a new anonymized version in O(n+logm) expected time, where n is the cardinality of the original dataset, and m the number of versions released previously. Both bounds are optimal under the realistic assumption that n ≫ m. 1.
On Skylining with Flexible Dominance Relation.
Abstract — Given a set of d dimensional objects, a skyline query finds the objects (“skyline”) that are not dominated by others. However, skylines do not always provide useful query results to users, and existing methods of various skyline queries have at least one of the following drawbacks: (1) the size of skyline objects can not be controlled, or can be only increased or only decreased but not both; (2) skyline objects do not have built-in ranks; (3) skylines do not reflect users ’ weights (preferences) at different dimensions. In this paper, we propose a unified approach, the ε-skyline, to effectively solve all three drawbacks. We explore the properties of ε-skylines and propose several different algorithms to compute ε-skylines. I.
On the Anonymization of Sparse High%2DDimensional Data.
Abstract — Existing research on privacy-preserving data publishing focuses on relational data: in this context, the objective is to enforce privacy-preserving paradigms, such as kanonymity and ℓ-diversity, while minimizing the information loss incurred in the anonymizing process (i.e. maximize data utility). However, existing techniques adopt an indexing- or clusteringbased approach, and work well for fixed-schema data, with low dimensionality. Nevertheless, certain applications require privacy-preserving publishing of transaction data (or basket data), which involves hundreds or even thousands of dimensions, rendering existing methods unusable. We propose a novel anonymization method for sparse highdimensional data. We employ a particular representation that captures the correlation in the underlying data, and facilitates the formation of anonymized groups with low information loss. We propose an efficient anonymization algorithm based on this representation. We show experimentally, using real-life datasets, that our method clearly outperforms existing state-of-the-art in terms of both data utility and computational overhead. I.
On Anti%2DCorruption Privacy Preserving Publication.
Abstract — This paper deals with a new type of privacy threat, called “corruption”, in anonymized data publication. Specifically, an adversary is said to have corrupted some individuals, if s/he has already obtained their sensitive values before consulting the released information. Conventional generalization may lead to severe privacy disclosure in the presence of corruption. Motivated by this, we advocate an alternative anonymization technique that integrates generalization with perturbation and stratified sampling. The integration provides strong privacy guarantees, even if an adversary has corrupted any number of individuals. We verify the effectiveness of the proposed technique through experiments with real data. I.
Dynamic anonymization accurate statistical analysis with privacy preservation.

Query answering techniques on uncertain and probabilistic data tutorial summary.
Uncertain data are inherent in some important applications, such as environmental surveillance, market analysis, and quantitative economics research. Due to the importance of those applications and the rapidly increasing amount of uncertain data collected and accumulated, analyzing large collections of uncertain data has become an important task and has attracted more and more interest from the database community. Recently, uncertain data management has become an emerging hot area in database research and development. In this tutorial, we systematically review some representative studies on answering various queries on uncertain and probabilistic data.
Preservation of proximity privacy in publishing numerical sensitive data.

Indexing%2C BDual Tree.

Nearest Neighbor Queries in Network Databases.
A frequent type of query in spatial networks  (e.g., road networks) is to find the K nearest  neighbors (KNN) of a given query object.
Queries in Spatio%2Dtemporal Databases%2C Time Parameterized.

Output perturbation with query relaxation.

The Bdual%2DTree indexing moving objects by space filling curves in the dual space.

Primal or dual which promises faster spatiotemporal search%3F
The existing predictive spatiotemporal indexes can be classified into two categories, depending on whether they are based on the primal or dual methodology. Although we have gained considerable empirical knowledge about various access methods, currently there is only limited understanding on the theoretical characteristics of the two methodologies. In fact, the experimental results in different papers even contradict each other, regarding the relative superiority of the primal and dual techniques. This paper presents a careful study on the query performance of general primal and dual indexes, and reveals important insight into the behavior of each technique. In particular, we mathematically establish the conditions that determine the superiority of each methodology, and provide rigorous justification for well-known observations that have not been properly explained in the literature. Our analytical findings also resolve the contradiction in the experiments of previous work. To appear in VLDB Journal.
Efficient temporal counting with bounded error.
This paper studies aggregate search in transaction time databases. Specifically, each object in such a database can be modeled as a horizontal segment, whose y-projection is its search key, and its x-projection represents the period when the key was valid in history. Given a query timestamp qt and a key range �qk, a count-query retrieves the number of objects that are alive at qt, and their keys fall in �qk. We provide a method that accurately answers such queries, with error less than 1 ε + ε · Nalive(qt), where Nalive(qt) is the number of objects alive at time qt, and ε is any constant in (0,1]. Denoting the disk page size as B, and n = N/B, our technique requires O(n) space, processes any query in O(logB n) time, and supports each update in O(logB n) amortized I/Os. As demonstrated by extensive experiments, the proposed solutions guarantee query results with extremely high precision (median relative error below 5%), while consuming only a fraction of the space occupied by the existing approaches that promise precise results. To appear in VLDB Journal.
On Multidimensional k%2DAnonymity with Local Recoding Generalization.
This paper presents the first theoretical study, on using local-recoding generalization (LRG) to compute a kanonymous table with quality guarantee. First, we prove that it is NP-hard both to find the table with the maximum quality, and to discover a solution with an approximation ratio at most 5/4. Then, we develop an algorithm with good balance between the approximation ratio and time complexity. The quality of our solution is verified by experiments. 1
M%2Dinvariance towards privacy preserving re%2Dpublication of dynamic datasets.

Continuous Constraint Query Evaluation for Spatiotemporal Streams.
Abstract. In this paper we study the evaluation of continuous constraint queries (CCQs) for spatiotemporal streams. A CCQ triggers an alert whenever a configuration of constraints between streaming events in space and time are satisfied. Consider, for instance, a server that receives updates from GPS-enabled agents that report their positions and other measurements (e.g., environmental readings). An example of CCQ is: “Alert whenever at least 5 readings closer than 5km to each other and within a time difference of 5 minutes report high pressures and low temperatures”. We model CCQs as Constraint Satisfaction Problems (CSPs) and develop solutions for their continuous evaluation. Our techniques (1) consider the fast arrival rate of incoming events, and (2) minimize the memory requirements, without using predefined window constraints, but by utilizing the structure of the queries. In order to show the merits of the proposed techniques, we implement a system prototype and evaluate it with real data. 1
Continuous Constraint Query Evaluation for Spatiotemporal Streams.
Abstract. In this paper we study the evaluation of continuous constraint queries (CCQs) for spatiotemporal streams. A CCQ triggers an alert whenever a configuration of constraints between streaming events in space and time are satisfied. Consider, for instance, a server that receives updates from GPS-enabled agents that report their positions and other measurements (e.g., environmental readings). An example of CCQ is: “Alert whenever at least 5 readings closer than 5km to each other and within a time difference of 5 minutes report high pressures and low temperatures”. We model CCQs as Constraint Satisfaction Problems (CSPs) and develop solutions for their continuous evaluation. Our techniques (1) consider the fast arrival rate of incoming events, and (2) minimize the memory requirements, without using predefined window constraints, but by utilizing the structure of the queries. In order to show the merits of the proposed techniques, we implement a system prototype and evaluate it with real data. 1
On Efficient Spatial Matching.
E-mail address:
Range search on multidimensional uncertain data.
In an uncertain database, every object o is associated with a probability density function, which describes the likelihood that o appears at each position in a multidimensional workspace. This article studies two types of range retrieval fundamental to many analytical tasks. Specifically, a nonfuzzy query returns all the objects that appear in a search region rq with at least a certain probability tq. On the other hand, given an uncertain object q, fuzzy search retrieves the set of objects that are within distance εq from q with no less than probability tq. The core of our methodology is a novel concept of “probabilistically constrained rectangle”, which permits effective pruning/validation of nonqualifying/qualifying data. We develop a new index structure called the U-tree for minimizing the query overhead. Our algorithmic findings are accompanied with a thorough theoretical analysis, which reveals valuable insight into the problem characteristics, and mathematically confirms the efficiency of our solutions. We verify the effectiveness of the proposed techniques with extensive
Efficient top%2Dk processing in large%2Dscaled distributed environments.

Random Sampling for Continuous Streams with Arbitrary Updates.

Efficient Skyline and Top%2Dk Retrieval in Subspaces.
Skyline and top-k queries are two popular operations for preference retrieval. In practice, applications that require these operations usually provide numerous candidate attributes, whereas, depending on their interests, users may issue queries regarding different subsets of the dimensions. The existing algorithms are inadequate for subspace skyline/top-k search because they have at least one of the following defects: they (i) require scanning the entire database at least once; (ii) are optimized for one subspace but incur significant overhead for other subspaces; (iii) demand expensive maintenance cost or space consumption. In this paper, we propose a technique, SUBSKY, which settles both types of queries using purely relational technologies. The core of SUBSKY is a transformation that converts multidimensional data to 1D values. These values are indexed by a simple B-tree, which allows us to answer subspace queries by accessing a fraction of the database. SUBSKY entails low maintenance overhead, which equals the cost of updating a traditional B-tree. Extensive experiments with real data confirm that our technique outperforms alternative solutions significantly in both efficiency and scalability. 1
Branch%2Dand%2Dbound processing of ranked queries.
Despite the importance of ranked queries in numerous applications involving multi-criteria decision making, they are not efficiently supported by traditional database systems. In this paper, we propose a simple yet powerful technique for processing such queries based on multidimensional access methods and branch-and-bound search. The advantages of the proposed methodology are: (i) it is space efficient, requiring only a single index on the given relation (storing each tuple at most once), (ii) it achieves significant (i.e., orders of magnitude) performance gains with respect to the current state-of-the-art, (iii) it can efficiently handle data updates, and (iv) it is applicable to other important variations of ranked search (including the support for non-monotone preference functions), at no extra space overhead. We confirm the superiority of the proposed methods with a detailed experimental study.
Multidimensional reverse k NN search.
Given a multi-dimensional point q, a reverse k nearest neighbor (RkNN) query retrieves all the data points that have q as one of their k nearest neighbors. Existing methods for processing such queries have at least one of the following deficiencies: they (i) do not support arbitrary values of k, (ii) cannot deal efficiently with database updates, (iii) are applicable only to 2D data but not to higher dimensionality, and (iv) retrieve only approximate results. Motivated by these shortcomings, we develop algorithms for exact RkNN processing with arbitrary values of k on dynamic, multi-dimensional datasets. Our methods utilize a conventional data-partitioning index on the dataset and do not require any pre-computation. As a second step, we extend the proposed techniques to continuous RkNN search, which returns the RkNN results for every point on a line segment. We evaluate the effectiveness of our algorithms with extensive experiments using both real and synthetic datasets.
Privacy Preserving Data Publication From Generalization to Anatomy.

Efficient Quantile Retrieval on Multi%2Ddimensional Data.
Abstract. Given a set of N multi-dimensional points, we study the computation of φ-quantiles according to a ranking function F, which is provided by the user at runtime. Specifically, F computes a score based on the coordinates of each point; our objective is to report the object whose score is the φN-th smallest in the dataset. φ-quantiles provide a succinct summary about the F-distribution of the underlying data, which is useful for online decision support, data mining, selectivity estimation, query optimization, etc. Assuming that the dataset is indexed by a spatial access method, we propose several algorithms for retrieving a quantile efficiently. Analytical and experimental results demonstrate that a branch-and-bound method is highly effective in practice, outperforming alternative approaches by a significant factor. 1
Processing Ranked Queries with the Minimum Space.
Abstract. Practical applications often need to rank multi-variate records by assigning various priorities to different attributes. Consider a relation that stores students ’ grades on two courses: database and algorithm. Student performance is evaluated by an “overall score ” calculated as w1·gdb+w2·galg,wherew1, w2 are two input “weights”, and gdb (galg) is the student grade on database (algorithm). A “top-k ranked query ” retrieves the k students with the best scores according to specific w1 and w2. We focus on top-k queries whose k is bounded by a constant c, and present solutions that guarantee low worst-case query cost by using provably the minimum space. The core of our methods is a novel concept, “minimum covering subset”, which contains only the necessary data for ensuring correct answers for all queries. Any 2D ranked search, for example, can be processed in O(log B(m/B)+c/B) I/Os using O(m/B) space, where m is the size of the minimum covering subset, and B the disk page capacity. Similar results are also derived for higher dimensionalities and approximate ranked retrieval. 1
SUBSKY Efficient Computation of Skylines in Subspaces.
Given a set of multi-dimensional points, the skyline contains the best points according to any preference function that is monotone on all axes. In practice, applications that require skyline analysis usually provide numerous candidate attributes, and various users depending on their interests may issue queries regarding different (small) subsets of the dimensions. Formally, given a relation with a large number (e.g.,&gt; 10) of attributes, a query aims at finding the skyline in an arbitrary subspace with a low dimensionality (e.g., 2). The existing algorithms do not support subspace skyline retrieval efficiently because they (i) require scanning the entire database at least once, or (ii) are optimized for one particular subspace but incur significant overhead for other subspaces. In this paper, we propose a technique SUBSKY which settles the problem using a single B-tree, and can be implemented in any relational database. The core of SUB-SKY is a transformation that converts multi-dimensional data to 1D values, and enables several effective pruning heuristics. Extensive experiments with real data confirm that SUBSKY outperforms alternative approaches significantly in both efficiency and scalability. 1
Mining distance%2Dbased outliers from large databases in any metric space.
Let R be a set of objects. An object o ∈ R is an outlier, if there exist less than k objects in R whose distances to o are at most r. The values of k, r, and the distance metric are provided by a user at the run time. The objective is to return all outliers with the smallest I/O cost. This paper considers a generic version of the problem, where no information is available for outlier computation, except for objects’ mutual distances. We prove an upper bound for the memory consumption which permits the discovery of all outliers by scanning the dataset 3 times. The upper bound turns out to be extremely low in practice, e.g., less than 1 % of R. Since the actual memory capacity of a realistic DBMS is typically larger, we develop a novel algorithm, which integrates our theoretical findings with carefullydesigned heuristics that leverage the additional memory to improve I/O efficiency. Our technique reports all outliers by scanning the dataset at most twice (in some cases, even once), and significantly outperforms the existing solutions by a factor up to an order of magnitude.
Personalized privacy preservation.
We study generalization for preserving privacy in publication of sensitive data. The existing methods focus on a universal approach that exerts the same amount of preservation for all persons, without catering for their concrete needs. The consequence is that we may be offering insufficient protection to a subset of people, while applying excessive privacy control to another subset. Motivated by this, we present a new generalization framework based on the concept of personalized anonymity. Our technique performs the minimum generalization for satisfying everybody’s requirements, and thus, retains the largest amount of information from the microdata. We carry out a careful theoretical study that leads to valuable insight into the behavior of alternative solutions. In particular, our analysis mathematically reveals the circumstances where the previous work fails to protect privacy, and establishes the superiority of the proposed solutions. The theoretical findings are verified with extensive experiments.  
Anatomy Simple and Effective Privacy Preservation.

Progressive Computation of the Min%2DDist Optimal%2DLocation Query.
This paper proposes and solves the min-dist optimal-location query in spatial databases. Given a set S of sites, a set O of weighted objects, and a spatial region Q, the min-dist optimal-location query returns a location in Q which, if a new site is built there, minimizes the average distance from each object to its closest site. This query can help a franchise (e.g. McDonald’s) decide where to put a new store in order to maximize the benefit to its customers. To solve this problem is challenging, for there are theoretically infinite number of locations in Q, all of which could be candidates. This paper first provides a theorem that limits the number of candidate locations without losing the power to find exact answers. Then it provides a progressive algorithm that quickly suggests a location, tells the maximum error it may have, and keeps refining the result. When the algorithm finishes, the exact answer can be found. The intermediate result of early runs can be used to prune the search space for later runs. Crucial to the pruning technique are novel lower-bound estimators. The proposed algorithm, the effect of several optimizations, and the progressiveness are experimentally evaluated. 1.
Towards multidimensional subspace skyline analysis.
The skyline operator is important for multicriteria decision-making applications. Although many recent studies developed efficient methods to compute skyline objects in a given space, none of them considers skylines in multiple subspaces simultaneously. More importantly, the fundamental
Spatial Query Estimation without the Local Uniformity Assumption.

Maintaining Sliding Window Skylines on Data Streams.
Abstract—The skyline of a multidimensional data set contains the “best ” tuples according to any preference function that is monotonic on each dimension. Although skyline computation has received considerable attention in conventional databases, the existing algorithms are inapplicable to stream applications because 1) they assume static data that are stored in the disk (rather than continuously arriving/expiring), 2) they focus on “one-time ” execution that returns a single skyline (in contrast to constantly tracking skyline changes), and 3) they aim at reducing the I/O overhead (as opposed to minimizing the CPU-cost and main-memory consumption). This paper studies skyline computation in stream environments, where query processing takes into account only a “sliding window ” covering the most recent tuples. We propose algorithms that continuously monitor the incoming data and maintain the skyline incrementally. Our techniques utilize several interesting properties of stream skylines to improve space/time efficiency by expunging data from the system as early as possible (i.e., before their expiration). Furthermore, we analyze the asymptotical performance of the proposed solutions, and evaluate their efficiency with extensive experiments. Index Terms—Skyline, stream, database, algorithm. 1
Reverse Nearest Neighbors in Large Graphs.
Abstract—A reverse nearest neighbor (RNN) query returns the data objects that have a query point as their nearest neighbor (NN). Although such queries have been studied quite extensively in Euclidean spaces, there is no previous work in the context of large graphs. In this paper, we provide a fundamental lemma, which can be used to prune the search space while traversing the graph in search for RNN. Based on it, we develop two RNN methods; an eager algorithm that attempts to prune network nodes as soon as they are visited and a lazy technique that prunes the search space when a data point is discovered. We study retrieval of an arbitrary number k of reverse nearest neighbors, investigate the benefits of materialization, cover several query types, and deal with cases where the queries and the data objects reside on nodes or edges of the graph. The proposed techniques are evaluated in various practical scenarios involving spatial maps, computer networks, and the DBLP coauthorship graph. Index Terms — Query processing, spatial databases, graphs and networks. 1
Reverse Nearest Neighbor Search in Metric Spaces.
Abstract—Given a set D of objects, a reverse nearest neighbor (RNN) query returns the objects o in D such that o is closer to a query object q than to any other object in D, according to a certain similarity metric. The existing RNN solutions are not sufficient because they either 1) rely on precomputed information that is expensive to maintain in the presence of updates or 2) are applicable only when the data consists of “Euclidean objects ” and similarity is measured using the L2 norm. In this paper, we present the first algorithms for efficient RNN search in generic metric spaces. Our techniques require no detailed representations of objects, and can be applied as long as their mutual distances can be computed and the distance metric satisfies the triangle inequality. We confirm the effectiveness of the proposed methods with extensive experiments. Index Terms—Reverse nearest neighbor, metric space. 1
Spatio%2Dtemporal join selectivity.
Moving objects databases managing spatial objects with continuously changing position and extent over time have recently found large interest in the database community. Queries about moving objects become particularly interesting when they ask for temporal changes in the topological relationships between evolving spatial objects. A concept of spatio-temporal predicates has been proposed to describe these relationships. The goal of this paper is to design efficient algorithms for them so that they can be used in spatiotemporal joins and selections. This paper proposes not to design an algorithm for each new predicate individually but to employ a generic algorithmic scheme which is able to cover present and future predicate definitions. 1.
Spatio%2Dtemporal join selectivity.
Moving objects databases managing spatial objects with continuously changing position and extent over time have recently found large interest in the database community. Queries about moving objects become particularly interesting when they ask for temporal changes in the topological relationships between evolving spatial objects. A concept of spatio-temporal predicates has been proposed to describe these relationships. The goal of this paper is to design efficient algorithms for them so that they can be used in spatiotemporal joins and selections. This paper proposes not to design an algorithm for each new predicate individually but to employ a generic algorithmic scheme which is able to cover present and future predicate definitions. 1.
Reverse Nearest Neighbors in Large Graphs.
Abstract—A reverse nearest neighbor (RNN) query returns the data objects that have a query point as their nearest neighbor (NN). Although such queries have been studied quite extensively in Euclidean spaces, there is no previous work in the context of large graphs. In this paper, we provide a fundamental lemma, which can be used to prune the search space while traversing the graph in search for RNN. Based on it, we develop two RNN methods; an eager algorithm that attempts to prune network nodes as soon as they are visited and a lazy technique that prunes the search space when a data point is discovered. We study retrieval of an arbitrary number k of reverse nearest neighbors, investigate the benefits of materialization, cover several query types, and deal with cases where the queries and the data objects reside on nodes or edges of the graph. The proposed techniques are evaluated in various practical scenarios involving spatial maps, computer networks, and the DBLP coauthorship graph. Index Terms — Query processing, spatial databases, graphs and networks. 1
Venn Sampling A Novel Prediction Technique for Moving Objects.
Given a region qR and a future timestamp qT, a “range aggregate ” query estimates the number of objects expected to appear in qR at time qT. Currently the only methods for processing such queries are based on spatiotemporal histograms, which have several serious problems. First, they consume considerable space in order to provide accurate estimation. Second, they incur high evaluation cost. Third, their efficiency continuously deteriorates with time. Fourth, their maintenance requires significant update overhead. Motivated by this, we develop Venn sampling (VS), a novel estimation method optimized for a set of “pivot queries ” that reflect the distribution of actual ones. In particular, given m pivot queries, VS achieves perfect estimation with only O(m) samples, as opposed to O(2 m) required by the current state of the art in workload-aware sampling. Compared with histograms, our technique is much more accurate (given the same space), produces estimates with negligible cost, and does not deteriorate with time. Furthermore, it permits the development of a novel “query-driven ” update policy, which reduces the update cost of conventional policies significantly. 1.
RPJ Producing Fast Join Results on Streams through Rate%2Dbased Optimization.

Probabilistic Spatial Queries on Existentially Uncertain Data.
Abstract. We study the problem of answering spatial queries in databases where objects exist with some uncertainty and they are associated with an existential probability. The goal of a thresholding probabilistic spatial query is to retrieve the objects that qualify the spatial predicates with probability that exceeds a threshold. Accordingly, a ranking probabilistic spatial query selects the objects with the highest probabilities to qualify the spatial predicates. We propose adaptations of spatial access methods and search algorithms for probabilistic versions of range queries and nearest neighbors and conduct an extensive experimental study, which evaluates the effectiveness of proposed solutions. 1
Catching the Best Views of Skyline A Semantic Approach Based on Decisive Subspaces.
The skyline operator is important for multicriteria decision making applications. Although many recent studies developed efficient methods to compute skyline objects in a specific space, the fundamental problem on the semantics of skylines remains open: Why and in which subspaces is (or is not) an object in the skyline? Practically, users may also be interested in the skylines in any subspaces. Then, what is the relationship between the skylines in the subspaces and those in the super-spaces? How can we effectively analyze the subspace skylines? Can we efficiently compute skylines in various subspaces? In this paper, we investigate the semantics of skylines, propose the subspace skyline analysis, and extend the full-space skyline computation to subspace skyline computation. We introduce a novel notion of skyline group which essentially is a group of objects that are coincidentally in the skylines of some subspaces. We identify the decisive subspaces that qualify skyline groups in the subspace skylines. The new notions concisely capture the semantics and the structures of skylines in various subspaces. Multidimensional roll-up and drilldown analysis is introduced. We also develop
Indexing Multi%2DDimensional Uncertain Data with Arbitrary Probability Density Functions.
In an “uncertain database”, an object o is associated with a multi-dimensional probability density function (pdf), which describes the likelihood that o appears at each position in the data space. A fundamental operation is the “probabilistic range search ” which, given a value pq and a rectangular area rq, retrieves the objects that appear in rq with probabilities at least pq. In this paper, we propose the U-tree, an access method designed to optimize both the I/O and CPU time of range retrieval on multi-dimensional imprecise data. The new structure is fully dynamic (i.e., objects can be incrementally inserted/deleted in any order), and does not place any constraints on the data pdfs. We verify the query and update efficiency of U-trees with extensive experiments. 1
Progressive skyline computation in database systems.
The skyline of a d-dimensional dataset contains the points that are not dominated by any other point on all dimensions. Skyline computation has recently received considerable attention in the database community, especially for progressive methods that can quickly return the initial results without reading the entire database. All the existing algorithms, however, have some serious shortcomings which limit their applicability in practice. In this article we develop branch-andbound skyline (BBS), an algorithm based on nearest-neighbor search, which is I/O optimal, that is, it performs a single access only to those nodes that may contain skyline points. BBS is simple to implement and supports all types of progressive processing (e.g., user preferences, arbitrary dimensionality, etc). Furthermore, we propose several interesting variations of skyline computation, and show how BBS can be applied for their efficient processing.
Aggregate nearest neighbor queries in spatial databases.
Given two spatial datasets P (e.g., facilities) and Q (queries), an aggregate nearest neighbor (ANN) query retrieves the point(s) of P with the smallest aggregate distance(s) to points in Q. Assuming, for example, n users at locations q1,... qn,anANN query outputs the facility p ∈ P that minimizes the sum of distances |pqi | for 1 ≤ i ≤ n that the users have to travel in order to meet there. Similarly, another ANN query may report the point p ∈ P that minimizes the maximum distance that any user has to travel, or the minimum distance from some user to his/her closest facility. If Q fits in memory and P is indexed by an R-tree, we develop algorithms for aggregate nearest neighbors that capture several versions of the problem, including weighted queries and incremental reporting of results. Then, we analyze their performance and propose cost models for query optimization. Finally, we extend our techniques for disk-resident queries and approximate ANN retrieval. The efficiency of the algorithms and the accuracy of the cost models are evaluated through extensive experiments with real and synthetic datasets.
Historical spatio%2Dtemporal aggregation.
Spatio-temporal databases store information about the positions of individual objects over time. However, in many applications such as traffic supervision or mobile communication systems, only summarized data, like the number of cars in an area for a specific period, or phone-calls serviced by a cell each day, is required. Although this information can be obtained from operational databases, its computation is expensive, rendering online processing inapplicable. In this paper, we present specialized methods, which integrate spatio-temporal indexing with pre-aggregation. The methods support dynamic spatio-temporal dimensions for the efficient processing of historical aggregate queries without a priori knowledge of grouping hierarchies. The superiority of the proposed techniques over existing methods is demonstrated through a comprehensive probabilistic analysis and an extensive experimental evaluation.
A Threshold%2DBased Algorithm for Continuous Monitoring of k Nearest Neighbors.
Abstract—Assume a set of moving objects and a central server that monitors their positions over time, while processing continuous nearest neighbor queries from geographically distributed clients. In order to always report up-to-date results, the server could constantly obtain the most recent position of all objects. However, this naïve solution requires the transmission of a large number of rapid data streams corresponding to location updates. Intuitively, current information is necessary only for objects that may influence some query result (i.e., they may be included in the nearest neighbor set of some client). Motivated by this observation, we present a threshold-based algorithm for the continuous monitoring of nearest neighbors that minimizes the communication overhead between the server and the data objects. The proposed method can be used with multiple, static, or moving queries, for any distance definition, and does not require additional knowledge (e.g., velocity vectors) besides object locations. Index Terms—Spatial databases, location-dependent and sensitive, query processing. 1
Approximate Temporal Aggregation.
Temporal aggregate queries retrieve summarized information about records with time-evolving attributes. Existing approaches have at least one of the following shortcomings: (i) they incur large space requirements, (ii) they have high processing cost and (iii) they are based on complex structures, which are not available in commercial systems. In this paper we solve these problems by approximation techniques with bounded error. We propose two methods: the first one is based on multiversion B-trees and has logarithmic worst-case query cost, while the second technique uses off-the-shelf B- and Rtrees, and achieves the same performance in the expected case. We experimentally demonstrate that the proposed methods consume an order of magnitude less space than their competitors and are significantly faster, even for cases that the permissible error bound is very small.
Querying about the Past%2C the Present%2C and the Future in Spatio%2DTemporal.
Moving objects (e.g., vehicles in road networks) continuously generate large amounts of spatio-temporal information in the form of data streams. Efficient management of such streams is a challenging goal due to the highly dynamic nature of the data and the need for fast, on-line computations. In this paper we present a novel approach for approximate query processing about the present, past, or the future in spatio-temporal databases. In particular, we first propose an incrementally updateable, multi-dimensional histogram for present-time queries. Second, we develop a general architecture for maintaining and querying historical data. Third, we implement a stochastic approach for predicting the results of queries that refer to the future. Finally, we experimentally prove the effectiveness and efficiency of our techniques using a realistic simulation. 1.
Group Nearest Neighbor Queries.
Given two sets of points P and Q, a group nearest neighbor (GNN) query retrieves the point(s) of P with the smallest sum of distances to all points in Q. Consider, for instance, three users at locations q1, q2 and q3 that want to find a meeting point (e.g., a restaurant); the corresponding query returns the data point p that minimizes the sum of Euclidean distances |pqi | for 1≤i≤3. Assuming that Q fits in memory and P is indexed by an R-tree, we propose several algorithms for finding the group nearest neighbors efficiently. As a second step, we extend our techniques for situations where Q cannot fit in memory, covering both indexed and non-indexed query points. An experimental evaluation identifies the best alternative based on the data and query properties. 1.
Spatio%2DTemporal Aggregation Using Sketches.
Several spatio-temporal applications require the retrieval of summarized information about moving objects that lie in a query region during a query interval (e.g., the number of mobile users covered by a cell, traffic volume in a district, etc.). Existing solutions have the distinct counting problem: if an object remains in the query region for several timestamps during the query interval, it will be counted multiple times in the result. The paper solves this problem by integrating spatio-temporal indexes with sketches, traditionally used for approximate query processing. The proposed techniques can also be applied to reduce the space requirements of conventional spatiotemporal data and to mine spatio-temporal association rules.
Group Nearest Neighbor Queries.
Given two sets of points P and Q, a group nearest neighbor (GNN) query retrieves the point(s) of P with the smallest sum of distances to all points in Q. Consider, for instance, three users at locations q1, q2 and q3 that want to find a meeting point (e.g., a restaurant); the corresponding query returns the data point p that minimizes the sum of Euclidean distances |pqi | for 1≤i≤3. Assuming that Q fits in memory and P is indexed by an R-tree, we propose several algorithms for finding the group nearest neighbors efficiently. As a second step, we extend our techniques for situations where Q cannot fit in memory, covering both indexed and non-indexed query points. An experimental evaluation identifies the best alternative based on the data and query properties. 1.
Mining%2C indexing%2C and querying historical spatiotemporal data.
Abstract—Given a large spatio-temporal database of events, where each event consists of the fields event ID, time, location, and event type, mining spatio-temporal sequential patterns identifies significant event-type sequences. Such spatio-temporal sequential patterns are crucial to the investigation of spatial and temporal evolutions of phenomena in many application domains. Recent research literature has explored the sequential patterns on transaction data and trajectory analysis on moving objects. However, these methods cannot be directly applied to mining sequential patterns from a large number of spatio-temporal events. Two major research challenges still remain: 1) the definition of significance measures for spatio-temporal sequential patterns to avoid spurious ones and 2) the algorithmic design under the significance measures, which may not guarantee the downward closure property. In this paper, we propose a sequence index as the significance measure for spatio-temporal sequential patterns, which is meaningful due to its interpretability using spatial statistics. We propose a novel algorithm called Slicing-STS-Miner to tackle the algorithmic design challenge using the spatial sequence index, which does not preserve the downward closure property. We compare the proposed algorithm with a simple algorithm called STS-Miner that utilizes the weak monotone property of the sequence index. Performance evaluations using both synthetic and real-world data sets show that the Slicing-STS-Miner is an order of magnitude faster than STS-Miner for large data sets. Index Terms—Spatio-temporal sequential pattern, density ratio, sequence index, slicing, performance. Ç 1
Prediction and Indexing of Moving Objects with Unknown Motion Patterns.
Existing methods for prediction in spatio-temporal databases assume that objects move according to linear functions. This severely limits their applicability, since in practice movement is more complex, and individual objects may follow drastically different motion patterns. In order to overcome these problems, we first introduce a general framework for monitoring and indexing moving objects, where (i) each object computes individually the function that accurately captures its movement and (ii) a server indexes the object locations at a coarse level and processes queries using a filter-refinement mechanism. Our second contribution is a novel recursive motion function that supports a broad class of non-linear motion patterns. The function does not presume any a-priori movement but can postulate the particular motion of each object by examining its locations at recent timestamps. Finally, we propose an efficient indexing scheme that facilitates the processing of predictive queries without false misses. 1.
All%2DNearest%2DNeighbors Queries in Spatial Databases.
Given two sets A and B of multidimensional objects, the all-nearest-neighbors (ANN) query retrieves for each object in A its nearest neighbor in B. Although this operation is common in several applications, it has not received much attention in the database literature. In this paper we study alternative methods for processing ANN queries depending on whether A and B are indexed. Our algorithms are evaluated through extensive experimentation using synthetic and real datasets. The performance studies show that they are an order of magnitude faster than a previous approach based on closest-pairs query processing. 1
Reverse kNN Search in Arbitrary Dimensionality.
Given a point q, a reverse k nearest neighbor (RkNN) query retrieves all the data points that have q as one of their k nearest neighbors. Existing methods for processing such queries have at least one of the following they are applicable only to 2D data (but not to higher dimensionality), and (iv) they retrieve only approximate results. Motivated by these shortcomings, we develop algorithms for exact processing of RkNN with arbitrary values of k on dynamic multidimensional datasets. Our methods utilize a conventional data-partitioning index on the dataset and do not require any pre-computation. In addition to their flexibility, we experimentally verify that the proposed algorithms outperform the existing ones even in their restricted focus.
Range Aggregate Processing in Spatial Databases.
Abstract—A range aggregate query returns summarized information about the points falling in a hyper-rectangle (e.g., the total number of these points instead of their concrete ids). This paper studies spatial indexes that solve such queries efficiently and proposes the aggregate Point-tree (aP-tree), which achieves logarithmic cost to the data set cardinality (independently of the query size) for two-dimensional data. The aP-tree requires only small modifications to the popular multiversion structural framework and, thus, can be implemented and applied easily in practice. We also present models that accurately predict the space consumption and query cost of the aP-tree and are therefore suitable for query optimization. Extensive experiments confirm that the proposed methods are efficient and practical. Index Terms—Database, spatial database, range queries, aggregation. 1
Performance Analysis of R%2A%2DTrees with Arbitrary Node Extents .
Abstract—Existing analysis for R-trees is inadequate for several traditional and emerging applications including, for example, temporal, spatio-temporal, and multimedia databases because it is based on the assumption that the extents of a node are identical on all dimensions, which is not satisfied in these domains. In this paper, we propose analytical models that can accurately predict R*-tree performance without this assumption. Our derivation is based on the novel concept of extent regression function, which computes the node extents as a function of the number of node splits. Detailed experimental evaluation reveals that the proposed models are accurate, even in cases where previous methods fail completely. Index Terms—Database, spatial database, R-tree, cost model. 1
The power%2Dmethod a comprehensive estimation technique for multi%2Ddimensional queries.
Existing estimation approaches for multi-dimensional databases often rely on the assumption that data distribution in a small region is uniform, which seldom holds in practice. Moreover, their applicability is limited to specific estimation tasks under certain distance metric. This paper develops the Power-method, a comprehensive technique applicable to a wide range of query optimization problems under various metrics. The Powermethod eliminates the local uniformity assumption and is accurate even in scenarios where existing approaches completely fail. Furthermore, it performs estimation by evaluating only one simple formula with minimal computational overhead. Extensive experiments confirm that the Powermethod outperforms previous techniques in terms of accuracy and applicability to various optimization scenarios. 1.

Selectivity Estimation for Predictive Spatio%2DTemporal Queries.
This paper proposes a cost model for selectivity estimation of predictive spatio-temporal window queries. Initially, we focus on uniform data proposing formulae that capture both points and rectangles, and any type of object/query mobility combination (i.e., dynamic objects, dynamic queries or both). Then, we apply the model to non-uniform datasets by introducing spatio-temporal histograms, which in addition to the spatial, also consider the velocity distributions during partitioning. The advantages of our techniques are (i) high accuracy (1-2 orders of magnitude lower error than previous techniques), (ii) ability to handle all query types, and (iii) efficient handling of updates.

An Optimal and Progressive Algorithm for Skyline Queries.
The skyline of a set of d-dimensional points contains the points that are not dominated by any other point on all dimensions. Skyline computation has recently received considerable attention in the database community, especially for progressive (or online) algorithms that can quickly return the first skyline points without having to read the entire data file. Currently, the most efficient algorithm is NN (nearest neighbors), which applies the divideand -conquer framework on datasets indexed by R-trees. Although NN has some desirable features (such as high speed for returning the initial skyline points, applicability to arbitrary data distributions and dimensions), it also presents several inherent disadvantages (need for duplicate elimination if d&gt;2, multiple accesses of the same node, large space overhead). In this paper we develop BBS (branch-and-bound skyline), a progressive algorithm also based on nearest neighbor search, which is IO optimal, i.e., it performs a single access only to those R-tree nodes that may contain skyline points. Furthermore, it does not retrieve duplicates and its space overhead is significantly smaller than that of NN. Finally, BBS is simple to implement and can be efficiently applied to a variety of alternative skyline queries. An analytical and experimental comparison shows that BBS outperforms NN (usually by orders of magnitude) under all problem instances.
Validity Information Retrieval for Spatio%2DTemporal Queries Theoretical Performance Bounds.
The results of traditional spatial queries (i.e., range search, nearest  neighbor, etc.) are usually meaningless in spatio-temporal applications, because  they will be invalidated by the movements of query and/or data objects. In practice,  a query result R should be accompanied with validity information specifying  (i) the (future) time T that R will expire, and (ii) the change C of R at time T  (so that R can be updated incrementally). Although several algorithms have  been proposed for this problem, their worst-case performance is the same as  that of sequential scan. This paper presents the first theoretical study on validity  queries, and develops indexes and algorithms with attractive I/O complexities.
Analysis of predictive spatio%2Dtemporal queries.
this paper we present probabilistic cost models that estimate the selectivity of spatio-temporal window queries and joins, and the expected distance between a query and its nearest neighbor(s). Our models capture any query/object mobility combination (moving queries, moving objects or both) and any data type (points and rectangles) in arbitrary dimensionality. In addition, we develop specialized spatio-temporal histograms, which take into account both location and velocity information, and can be incrementally maintained. Extensive performance evaluation verifies that the proposed techniques produce highly accurate estimation on both uniform and non-uniform data
The TPR%2A%2DTree An Optimized Spatio%2DTemporal Access Method for Predictive Queries.
A predictive spatio-temporal query retrieves the  set of moving objects that will intersect a query  window during a future time interval. Currently,  the only access method for processing such  queries in practice is the TPR-tree. In this paper  we first perform an analysis to determine the  factors that affect the performance of predictive  queries and show that several of these factors are  not considered by the TPR-tree, which uses the  insertion/deletion algorithms of the R*-tree  designed for static data. Motivated by this, we  propose a new index structure called the TPR*-  tree, which takes into account the unique features  of dynamic objects through a set of improved  construction algorithms. In addition, we provide  cost models that determine the optimal  performance achievable by any data-partition  spatio-temporal access method. Using  experimental comparison, we illustrate that the  TPR*-tree is nearly-optimal and significantly  outperforms the TPR-tree under all conditions.
Query Processing in Spatial Network Databases.
Despite the importance of spatial networks in  real-life applications, most of the spatial database  literature focuses on Euclidean spaces. In this  paper we propose an architecture that integrates  network and Euclidean information, capturing  pragmatic constraints. Based on this architecture,  we develop a Euclidean restriction and a  network expansion framework that take  advantage of location and connectivity to  efficiently prune the search space. These  frameworks are successfully applied to the most  popular spatial queries, namely nearest  neighbors, range search, closest pairs and edistance   joins, in the context of spatial network  databases.
Spatial queries in dynamic environments.
this paper we formulate two novel query types, time parameterized and continuous queries, applicable in such environments. A timeparameterized query retrieves the actual result at the time when the query is issued, the expiry time of the result given the current motion of the query and database objects, and the change that causes the expiration. A continuous query retrieves tuples of the form &lt;result, interval&gt;, where each result is accompanied by a future interval, during which it is valid. We study time-parameterized and continuous versions of the most common spatial queries (i.e., window queries, nearest neighbors, spatial joins), proposing efficient processing algorithms and accurate cost models
Analysis of predictive spatio%2Dtemporal queries.
this paper we present probabilistic cost models that estimate the selectivity of spatio-temporal window queries and joins, and the expected distance between a query and its nearest neighbor(s). Our models capture any query/object mobility combination (moving queries, moving objects or both) and any data type (points and rectangles) in arbitrary dimensionality. In addition, we develop specialized spatio-temporal histograms, which take into account both location and velocity information, and can be incrementally maintained. Extensive performance evaluation verifies that the proposed techniques produce highly accurate estimation on both uniform and non-uniform data
Recent Progress on Selected Topics in Database Research %2D A Report by Nine Young Chinese Researchers Working in the United States.

Aggregate Processing of Planar Points.
Aggregate window queries return summarized information about objects  that fall inside a query rectangle (e.g., the number of objects instead of  their concrete ids). Traditional approaches for processing such queries usually  retrieve considerable extra information, thus compromising the processing cost.
Indexing Spatio%2DTemporal Data Warehouses.
Spatio-temporal databases store information about the positions of individual objects over time. In many applications however, such as traffic supervision or mobile communication systems, only summarized data, like the average number of cars in an area for a specific period, or phones serviced by a cell each day, is required. Although this information can be obtained from operational databases, its computation is expensive, rendering online processing inapplicable. A vital solution is the construction of a spatiotemporal data warehouse. In this paper, we describe a framework for supporting OLAP operations over spatiotemporal data. We argue that the spatial and temporal dimensions should be modeled as a combined dimension on the data cube and present data structures, which integrate spatiotemporal indexing with pre-aggregation. While the well-known materialization techniques require a-priori knowledge of the grouping hierarchy, we develop methods that utilize the proposed structures for efficient execution of ad-hoc group-bys. Our techniques can be used for both static and dynamic dimensions.  1. 
Cost Models for Overlapping and Multi%2DVersion B%2DTrees.
Overlapping and multi-version techniques are two popular frameworks that transform an ephemeral index into a multtle logical-tree structure in order to support versioning databases. Although both frameworks have produced numerous effcient indexing methods, their performance analysis is rather limited; as a result there is no clear understanding about the behavior of the alternative structures and the choice of the best one, given the data and query characteristics. Furthermore, query optimization based on these methods is currently impossible. These are serious problems due to the incorporation of overlapping and multi-version techniques in several traditional (e.g., banking) and emerging (e.g., spatio-temporaO applications. In this paper, we propose frameworks for reducing performance analysis of overlapping and multi-version structures to that of the corresponding ephemeral structures, thus simpliing the problem significantly. The frameworks lead to accurate cost models that predict the sizes of the trees, the node accesses and query selectivity. Although we focus on B-tree-based structures, the proposed models can be employed with a variety of indexes.
Time%2Dparameterized queries in spatio%2Dtemporal databases.
Time-parameterized queries (TP queries for short) retrieve (i) the actual result at the time that the query  is issued, (ii) the validity period of the result given the current motion of the query and the database  objects, and (iii) the change that causes the expiration of the result. Due to the highly dynamic nature of  several spatio-temporal applications, TP queries are important both as standalone methods, as well as  building blocks of more complex operations. However, little work has been done towards their efficient  processing. In this paper, we propose a general framework that covers time-parameterized variations of  the most common spatial queries, namely window queries, k-nearest neighbors and spatial joins. In  particular, each of these TP queries is reduced to nearest neighbor search where the distance functions  are def&#039;med according to the query type. This reduction allows the application and extension of  well-known branch and bound techniques to the current problem. The proposed methods can be applied  with mobile queries, mobile objects or both, given a suitable indexing method. Our experimental  evaluation is based on R-trees and their extensions for dynamic objects.
Adaptive Index Structures.
Traditional indexes aim at optimizing the node  accesses during query processing, which,  however, does not necessarily minimize the total  cost due to the possibly large number of random  accesses. In this paper, we propose a general  framework for adaptive indexes that improve  overall query cost. The performance gain is  achieved by allowing index nodes to contain a  variable number of disk pages. Update  algorithms dynamically re-structure adaptive  indexes depending on the data and query  characteristics. Extensive experiments show that  adaptive B- and R-trees significantly outperform  their conventional counterparts, while incurring  minimal update overhead.
Continuous Nearest Neighbor Search.
A continuous nearest neighbor query retrieves  the nearest neighbor (NN) of every point on a  line segment (e.g., &#034;find all my nearest gas  stations during my route from point s to point  e&#034;). The result contains a set of &lt;point, interval&gt;  tuples, such that point is the NN of all points in  the corresponding interval. Existing methods for  continuous nearest neighbor search are based on  the repetitive application of simple NN  algorithms, which incurs significant overhead. In  this paper we propose techniques that solve the  problem by performing a single query for the  whole input segment. As a result the cost,  depending on the query and dataset  characteristics, may drop by orders of magnitude.
Adaptive Index Structures.
Traditional indexes aim at optimizing the node  accesses during query processing, which,  however, does not necessarily minimize the total  cost due to the possibly large number of random  accesses. In this paper, we propose a general  framework for adaptive indexes that improve  overall query cost. The performance gain is  achieved by allowing index nodes to contain a  variable number of disk pages. Update  algorithms dynamically re-structure adaptive  indexes depending on the data and query  characteristics. Extensive experiments show that  adaptive B- and R-trees significantly outperform  their conventional counterparts, while incurring  minimal update overhead.
Cost models for overlapping and multiversion structures.

Indexing and Retrieval of Historical Aggregate Information about Moving Objects.
Spatio-temporal databases store information about the positions of individual objects over time. In many applications however, such as traffic supervision or mobile communication systems, only summarized data, like the average number of cars in an area for a specific period, or phones serviced by a cell each day, is required. Although this information can be obtained from operational databases, its computation is expensive, rendering online processing inapplicable. A vital solution is the construction of a spatiotemporal data warehouse. In this paper, we describe a framework for supporting OLAP operations over spatiotemporal data. We argue that the spatial and temporal dimensions should be modeled as a combined dimension on the data cube and present data structures, which integrate spatiotemporal indexing with pre-aggregation. While the well-known materialization techniques require a-priori knowledge of the grouping hierarchy, we develop methods that utilize the proposed structures for efficient execution of ad-hoc group-bys. Our techniques can be used for both static and dynamic dimensions. 1
Efficient Historical R%2Dtrees.

Efficient OLAP Operations in Spatial Data Warehouses.
Spatial databases store information about the position of individual objects in space. In many  applications however, such as traffic supervision or mobile communications, only  summarized data, like the number of cars in an area or phones serviced by a cell, is required.  Although this information can be obtained from transactional spatial databases, its  computation is expensive, rendering online processing inapplicable. Driven by the non-spatial  paradigm, spatial data warehouses can be constructed to accelerate spatial OLAP operations.  In this paper we consider the star-schema and we focus on the spatial dimensions. Unlike the  non-spatial case, the groupings and the hierarchies in spatial dimensions can be numerous and  unknown at design time, therefore the well-known materialization techniques are not directly  applicable. In order to address this problem, we construct an ad-hoc grouping hierarchy based  on the spatial index at the finest spatial granularity. We incorporate this...
MV3R%2DTree A Spatio%2DTemporal Access Method for Timestamp and Interval Queries.

